package com.bascker.algorithm.practice.dp;

/**
 * 爬楼梯:
 *   假设你正在爬楼梯, 需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ Note：给定 n 是一个正整数。
 *
 * Note：给定 n 是一个正整数。
 *
 * @apiNote from leetcode T70
 * @implNote https://gitee.com/bascker/algorithm/wikis/1%E3%80%81%E7%88%AC%E6%A5%BC%E6%A2%AF?sort_id=2981417
 * @author bascker
 */
public class ClimbStairs {

    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }

        // dpi1 维护 dp(i - 1) 的值，dpi2 维护 dp(i - 2) 的值，dp 是最终结果。
        int dpi1 = 2, dpi2 = 1, dp = 0;
        for (int i = 3; i <= n; ++i) {
            dp = dpi1 + dpi2;
            dpi2 = dpi1;
            dpi1 = dp;
        }

        return dp;
    }

}
